package Hot_100;

import java.util.ArrayList;
import java.util.Stack;

/*
    98. 验证二叉搜索树
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    有效 二叉搜索树定义如下：
        节点的左子树只包含 小于 当前节点的数。
        节点的右子树只包含 大于 当前节点的数。
        所有左子树和右子树自身必须也是二叉搜索树。

     方法1：深搜
        一个结点的左孩子的权值应该小于该结点，右孩子权值应该大于该结点，但是具备这些条件还不满足二叉搜索树：
         如果root是其父节点的右孩子，root的左孩子还必须要大于root的父节点
         如果root是其父节点的左孩子，root的右孩子还必须要小于root的父节点
         比如 [5,4,6,null,null,3,7]
         所以保存结点的左右边界就很有必要了
             对于左孩子：上界是它的父节点，下界是它的父节点的下界
             对于右孩子：上界是它的父节点的上界，下界是它的父节点

     方法2：中序遍历
        二叉搜索树按照中序遍历得到的是一个升序序列的数组
        可以按照中序遍历的先后顺序依次将各个结点加入列表中
        每次新加入之前，去列表最后一个元素，看看是否大于它，如果大于就继续下去
        如果不大于就可以退出了；说白了就是转成中序遍历的问题了
* */
public class T98_isValidBST {
    //方法1：深搜
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    public boolean isValidBST(TreeNode root, Integer low, Integer high) {
        if (root == null) {
            return true;
        }

        if (low != null && root.val <= low) { //根结点比下边界还小
            return false;
        }

        if (high != null && root.val >= high) {//根结点比上边界还大
            return false;
        }

        //左子树递归
        if (!isValidBST(root.left, low, root.val)) {//上界是它的父节点，下界是它的父节点的下界
            return false;
        }

        //右子树递归
        if (!isValidBST(root.right, root.val, high)) {//上界是它的父节点的上界，下界是它的父节点
            return false;
        }
        return true;
    }

    //方法2：中序遍历（递归实现）
    boolean flag = true;

    public boolean isValidBST_1(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        inorder(root, list);
        return flag;
    }

    public void inorder(TreeNode root, ArrayList<TreeNode> list) {
        if (!flag) {     //已经不是升序就没必要再执行下去了
            return;
        }

        if (root == null) {
            return;
        }

        inorder(root.left, list);
        if (list.size() != 0 && list.get(list.size() - 1).val >= root.val) { //不符合升序
            flag = false;
            return;
        }

        list.add(root);
        inorder(root.right, list);
    }

    //方法2 中序遍历 (迭代实现)
    public boolean isValidBST_2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<TreeNode> list = new ArrayList<>();

//        Hot_100.TreeNode left = root.left; //需要先保留一下左结点
//        stack.push(root);
//        while (!stack.isEmpty()) {
//        }

        while (root != null || !stack.isEmpty()) {  //其实root在循环外先入栈和在循环后入栈是一样的效果的，反正不要弹出
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if (list.size() != 0 && list.get(list.size() - 1).val >= node.val) {
                return false;
            }
            list.add(node);

            root = node.right;
        }

        return true;
    }

    //方法2 中序遍历 Mirror

}